Software of the Month Club 1996 October/Software of the Month Club 1996 October.iso/mac/Education/LifeLab 3.1/Patterns/Dean Hickerson/RLE patterns/pattern list

Text File | 1993-09-13 | 20.9 KB | 464 lines | [TEXT/ttxt]

Large Life patterns
===================
This is a list of some of the patterns that I and others have built
during the past several years.  All of these are available from me
in RLE form.  I have some other patterns which aren't listed here
because I haven't gotten around to converting them to RLE or writing
headers for them.  If there's some pattern you've heard about and
would like to see, ask me; I'll see what I can do.

For each pattern, I've listed the name, discoverer/inventor (if not
me), discovery date, size of the RLE file, and a brief description.

Please report any errors that you find in this list.

          Dean Hickerson
          [e-mail]
          5/31/93  (last update 11/3/93)


Oscillators
-----------
Oscillator collection   (5/18/92; 26121 bytes)
     A collection of 115 oscillators, found by various people and
     programs, with periods from 3 to 690.

Venetian blinds   (9/13/92; 2677 bytes)
     A finite version of the infinite p2 oscillator whose rows
     alternate ..., full, full, empty, empty, full, full, ...

Crystal & decay 2700   (3/27/90; 1025 bytes)
     A p150 glider stream alternately crystallizes and decays.  Any
     period of the form  750 + 1950n  (n>=0)  can be obtained.

Crystal & decay 6600   (3/27/90; 1025 bytes)
     Larger version of the above.

Period 155   (4/20/92; 9911 bytes)
     Based on David Buckingham's B-heptomino turns, but using p5
     oscillators instead of p8.

Metamorphosis   (by Bob Wainwright, before 3/31/90; 1283 bytes)
     A symmetric p46 glider and LWSS shuttle; gliders turn into LWSSs
     by hitting p46 sparks (a reaction found by Bill Gosper); pairs of
     LWSSs turn into pairs of gliders on the line of symmetry.

3-sided glider-LWSS loop   (3/28/93; 580 bytes)
     Another p46 shuttle, using Gosper's 135 degree glider -> LWSS
     reflection, a 135 degree LWSS -> glider reflection, and a 90
     degree glider -> glider reflection.

Back and forth fuse   (11/3/93; 2675 bytes)
     A p1200 oscillator based on a fuse in which a pi heptomino
     moves along a line of blinkers spaced 17 units apart.


Pushers & Sqrtguns
------------------
     The first block pusher was built to answer the question "Is there
     a pattern in which some cells never become periodic, but whose
     population is bounded?".

     A pusher consists of a shotgun, a suppression point, a detector,
     and a block (or whatever).  The shotgun produces glider salvos
     which are normally deleted at the suppression point.  But
     sometimes one is allowed to escape.  The salvo eventually hits
     the block, pushing it farther away and sending a glider back
     toward the shotgun.  The detector detects the returning glider
     and allows one salvo to escape past the suppression point.  Since
     the round trip time keeps increasing, points along the glider
     paths never become periodic.  But the population is bounded.

     A sqrtgun is similar, but whenever a return glider is detected,
     another glider is released.  Eventually these gliders dominate
     the population, which is asymptotically proportional to sqrt(t).

Block pusher 5   (4/16/91; 2264 bytes)
     Uses a 3 glider salvo to push the block 10 units and return 2
     gliders.  (The second one slightly complicates the design of the
     detector.)

Sqrtgun 10.1   (2/14/91; 3001 bytes)
     A sqrtgun based on the above.  No additional logic was required,
     just a rearrangement to allow a glider that was already being
     produced to escape.

Sqrtgun 3.0   (1/28/91; 3186 bytes)
     Uses a 4 glider salvo to push a blinker 3 units and return a
     glider.  (The corresponding "blinker pusher" can be built be
     adding an eater to delete the escaping gliders.)


Sawteeth
--------
     A sawtooth pattern is one whose population is unbounded but
     does not tend to infinity.  The "expansion factor" (e.f.) of a
     sawtooth is the limiting ratio between the times of successive
     population maxima.

Orthogonal sawtooth with e.f. 21   (4/10/91; 3465 bytes)
     The first sawtooth built.  A shotgun fires a HWSS and pairs of
     LWSSs at the back of a c/3 spaceship ("turtle").  The HWSS turns
     into a loaf, which is pulled back by the LWSSs.  (A salvo that
     can pull this way is called a "tractor beam".)  When it reaches
     the shotgun, another HWSS is fired.  The population maxima occur
     in gens around t=18*21^n, at which time the population is
     about 7t/60; the minima occur around gens 6*21^n.

Orthogonal sawtooth with e.f. 11   (5/15/92; 2851 bytes)
     A simpler version of the above, using a p9 c/3 spaceship found
     by David Bell.  The HWSS is not necessary; the LWSSs create the
     loaf without it.

Orthogonal sawtooth with e.f. 6   (8/14/92; 2080 bytes)
     Similar to the above, but using a c/4 spaceship found by
     Hartmut Holzwart.

Diagonal sawtooth with e.f. 6   (5/14/91; 1640 bytes)
     Another tractor beam sawtooth:  A 2 glider salvo creates and
     pulls a block after hitting the back of a Cordership.

Parabolic sawtooth   (6/26/91; 3522 bytes)
     In this pattern, the maxima on the graph of population as a
     function of time occur on a parabola rather than a straight
     line as is the case for other sawteeth.  The pattern is a
     combination of a block pusher and a tractor beam.  The e.f.
     is 1; the population maxima occur around gens 20 n^2 + 144 n,
     at which time the population is about sqrt(t/180); the minima
     occur around 20 n^2 + 180 n.

Orthogonal sawtooth with e.f. 25   (8/26/92; 5933 bytes)
     A shotgun produces LWSS salvos.  Some are deleted; the others
     eventually reflect off the backs of a pair of c/3 spaceships,
     forming westward MWSSs.  Each MWSS causes the deletion of 5
     salvos.  The region between the shotgun and the c/3s alternately
     becomes full and empty of spaceships.

Diagonal sawtooth with e.f. 4   (by David Bell, 8/29/92; 2754 bytes)
     Same idea as the above, but more efficient:  Gliders reflect off
     the backs of 2 Corderships; each returning glider deletes 2
     outgoing ones.

Hacksaw   (7/8/92; 3235 bytes)
     This is an orthogonal sawtooth with expansion factor 9.  A
     period 8 c/2 blinker puffer moves east.  An eastward shotgun
     fires a 3 spaceship salvo at the west end of the blinker line,
     causing it to decay at 2c/3.  When the decay catches up with the
     puffer, a glider is emitted and the blinker puffer starts a new
     line of blinkers.  The glider hits another puffer, causing it to
     send a LWSS to the west.  When the LWSS reaches the shotgun,
     another salvo is emitted.

Sawtooth with external timing   (by David Bell, 10/27/92; 4208 bytes)
     This is an orthogonal sawtooth with expansion factor 2.  A
     period 8 c/2 blinker puffer moves west.  A cabertosser (see below
     in section "Weird growth rates") produces gliders with increasing
     gaps between them.  Each glider causes a 3 spaceship salvo (as in
     hacksaw) to be sent west.  The salvo causes the blinker line to
     decay.


Irrational growth rates
-----------------------
     The population of a gun or puffer grows linearly, with a rational
     average growth rate.  (More precisely, if P is the period of the
     gun or puffer, and  0 <= k < P  is a fixed integer, then the
     population in gen  t = k + nP  is asymptotic to  Ct,  where C may
     depend on k.)  Obtaining linear growth with an irrational growth
     rate is more difficult.

Irrational 5   (5/12/91; 2270 bytes)
     Two puffers travel east, one creating boats and the other sending
     MWSSs west.  Similarly, two puffers travel west, making boats
     and eastward MWSSs.  When a MWSS hits a boat, it deletes a MWSS
     from the opposing stream.  This results in the MWSS streams being
     thinned by a factor of  (sqrt(5)-1)/2.  The population in gen t
     is asymptotic to  (8 - 31 sqrt(5)/10) t.

Irrational 2   (5/20/91; 2083 bytes)
     Similar to the above, but when a westward MWSS hits a boat it
     destroys 2 eastward MWSSs.  The population in gen t appears to
     be asymptotic to  (78 sqrt(2) - 73)t/40  for t even, and
     (82 sqrt(2) - 77)t/40 for t odd, but that hasn't been proved.

Unknown irrational   (6/16/91; 1420 bytes)
     A similar pattern that's smaller but messier.  I can't even guess
     what its growth rate is.


Breeders
--------
     A breeder is any pattern whose population grows quadratically;
     i.e. for some positive number C, the population in gen t is
     greater than  C t^2  for all t.  The breeders that have been
     built all consist of a single component X, which periodically
     produces components Y, which periodically produce components Z.
     Thus the number of Ys is proportional to t and the number of Zs
     is proportional to t^2.  Breeders can be classified by stating
     whether or not X, Y, and Z move.  There are 4 obvious types:
          SMM     A gun produces puffers which produce gliders.
          MSM     A puffer produces guns which produce gliders.
          MMS     A puffer produces puffers (moving in a different
               direction) which produce stationary objects.
          MMM     A puffer produces puffers (moving in a different
               direction) which produce gliders.
     Most of the breeders that have been built are of type MSM.
     David Buckingham and Mark Niemiec have built some of the others,
     but I don't have copies of them.

The original breeder   (by Bill Gosper, 1970; 5733 bytes)
     The original breeder, as reconstructed by Jon Bennett from the
     photograph in Gardner's "Wheels, Life and Other Mathematical
     Amusement's", and shrunk by Dean Hickerson.  Ten p64 puffers
     move east, producing p30 glider guns aimed northeast.

p60 forward breeder   (12/8/91; 1625 bytes)
     One of 2 smallest known breeders, with initial population 603.
     Several p60 puffers move east, creating p30 guns aimed southeast.

p60 backward breeder   (12/8/91; 1621 bytes)
     Same as above, except the guns are aimed southwest.

Pufferless breeder   (10/12/92; 8949 bytes)
     This is of type S(M&M)M:  Stationary guns produce 8 eastward
     streams of spaceships and a stream of gliders.  Each glider
     bounces back and forth (NE and SE) among the spaceship streams,
     without damaging the spaceships, and releasing an extra glider
     at each bounce.


Guns
----
p120 glider gun   (1/14/91; 562 bytes)
     Smallest known p120 gun, made from a p60 gun and a blocker.

p120 LWSS gun   (1/28/91; 841 bytes)
     Smallest known p120 LWSS gun, made from a p30 LWSS gun, a
     middleweight emulator, and a blocker.

p46 bigun   (by Bill Gosper, date unknown; 178 bytes)
     A symmetric collision of 2 p46 shuttles produces 2 gliders.

p44 glider gun   (by David Buckingham, 4/2/92; 664 bytes)
     Gliders are produced by a collision of 2 large sparks from
     p44 oscillators.

pseudo p23 glider gun   (first discoverer and date unknown; 569 bytes)
     Outputs of 2 p46 guns are merged to produce a p23 glider stream.

pseudo p15 gun   (designed by David Buckingham, about 4/27/92;
                  implemented by Dean Hickerson, 5/5/92; 8019 bytes)
     Starting with a p30 glider stream, 3 p90 devices insert extra
     gliders to produce a p15 stream.

p92 glider gun   (1/8/91; 392 bytes)
     Built from 2 overlapping p46 guns whose streams cross in an
     eater-assisted ternary reaction.

cyclotron (p874 glider gun)   (7/22/92; 2685 bytes)
     Based on a 3 glider collision that produces 4 blocks, 4 beehives,
     8 blinkers, and 13 gliders.  Period 46 shuttles redirect gliders
     to make the collision happen again.

p168 4-barrelled glider gun   (by David Buckingham, before 11/20/91;
                               1351 bytes)
     One of the simplest examples of Buckingham's B-heptomino based
     gun construction method:  He found ways to use p8 oscillators
     to make a B-heptomino rotate 90 degrees in either 64, 65, or 73
     generations.  The 73 generation turn can produce a glider.  By
     combining these, a gun can be built with any period divisible by
     8 and >= 136.  In this one, 5 Bs move around a closed track made
     of 4 64 gen turns and 8 73 gen turns.

p136 12-barrelled glider gun   (11/23/91; 5907 bytes)
     Based on the above: 29 Bs move around a track made of 16 64 gen
     turns and 40 73 gen turns.

p152 2-barrelled glider gun   (11/25/91; 3697 bytes)
     Based on the above: 12 Bs move around a track made of 12 64 gen
     turns, 14 65 gen turns, and 2 73 gen turns.

p144 4-barrelled glider gun (by David Buckingham, 11/21/91;
                             2470 bytes)
     Two copies of a p72 oscillator found by Wainwright together with
     a blocker and 2 eaters can reflect and duplicate a glider.  One
     glider emerges in the same direction as the original; the other
     is turned 90 degrees.  By putting together 4 such reflectors, a
     4-barrelled gun can be built with period 144+72N for any N>=0.

p94 glider gun   (6/25/90; 5893 bytes)
     Based on the "AK47" reaction, discovered independently by David
     Buckingham and Richard Schroeppel, in which a honey farm
     predecessor is catalyzed to form gliders, traffic lights, and a
     new honey farm predecessor.  36 AK47s are used in order to
     suppress the traffic lights.

p500 glider gun   (by David Buckingham, 11/17/92; 3131 bytes)
     Based on a reaction in which 2 gliders become 3.  The 2 gliders
     hit a block, forming an R-pentomino which, catalyzed by a snake,
     2 blocks, a ship, and an eater, re-forms the block and produces
     3 gliders.  The gun contains 4 copies of this reaction; 4 of the
     12 output gliders escape, the other 8 are reflected from
     centinals (a p100 oscillator found by Bill Gosper) to cause the
     reactions to repeat.


Weird growth rates
------------------
Caber tosser   (5/1/91; 1572 bytes)
     Population is asymptotic to  C log(t),  where  C = 5/log(2).  A
     glider bounces back and forth between a Cordership and a fixed
     reflector; the round trip time doubles with each trip.  Whenever
     the glider hits the fixed reflector, an extra glider is created;
     these gliders eventually dominate the population.

log(t)^2   (4/24/92; 4444 bytes)
     This uses a caber tosser, a modified block pusher, and a
     toggleable p120 gun.  Each glider from the caber tosser turns on
     the gun and causes the block pusher to go through one cycle
     (sending out a salvo and awaiting the return gliders).  When the
     cycle is complete, the gun is turned back off.  This results in a
     population asymptotic to  C log(t)^2,  where  C = 5/(3 log(2)^2).

t log(t)   (11/13/90; 14251 bytes)
     Three breeders and two puffers create a sequence of large period
     guns; the N'th gun has period 240N.  At time t there are about
     t/60 finished guns, which have emitted about t/(240*1) + t/(240*2)
     + t/(240*3) + ... + t/(240*(t/60)) ~ t log(t)/240 gliders.

t log(t) by stifled breeder   (2/11/92; 4371 bytes)
     A modified exponential aperiodic pattern generates a LWSS about
     gen  20*3^N.  Meanwhile, a breeder produces a line of "stifled"
     guns, with eaters suppressing their outputs.  Each LWSS destifles
     one gun.  So in gen t there are about  log(t)/log(3)  active
     guns, which have emitted about  t log(t)/(30 log(3))  gliders.

t log(t)^2   (4/10/91; 6222 bytes)
     About gen  20*3^N,  a bounce occurs in a modified exponential
     aperiodic pattern.  This bounce turns on a MWSS gun and sends a
     glider toward a diagonal line of boats, as in the linear
     aperiodic pattern.  The MWSSs destifle guns produced by a stifled
     breeder.  When a glider returns from the nearest boat, the MWSS
     gun is turned off, having produced  N+1  MWSSs.  So, in gen t,
     about  log(t)/log(3)  MWSS pulses have occurred, activating about
     log(t)^2 / (2 log(3)^2)  guns, which have produced about
     t log(t)^2 / (60 log(3)^2)  gliders.

Clean t^(3/2)   (12/6/91; 3095 bytes)
     A breeder moves north, producing glider guns aimed southeast.
     A northward puffer produces eaters which catch the outputs of all
     guns except the first.  Two puffers move east, producing toads
     and boats.  When the glider stream from the N'th gun reaches the
     N'th toad, the first glider reflects northeast, hits the N'th
     boat, and reflects northwest.  Eventually it deletes the eater
     on the (N+1)'th gun, releasing another glider stream.  The N'th
     gun becomes active about gen  120 N^2.  So in gen t there are
     about  sqrt(t/120)  active guns, which have emitted about  t/30 +
     (t - 120)/30 + (t - 120 2^2)/30 + ... + (t - 120 sqrt(t/120)^2)
     ~  t^(3/2) / (45 sqrt(120)  gliders.

Messy t^(3/2)   (12/14/90; 3002 bytes)
     An earlier, messier, and slightly smaller version of the
     preceding.


Miscellaneous
-------------
Primer   (11/1/91; 7680 bytes)
     A LWSS escapes around generation  120n+100  if and only if n
     is prime.

Wickstretcher   (by Hartmut Holzwart & Dean Hickerson, 11/23/92;
                 686 bytes)
     A wick which appears to move east at c is emitted by a c/4
     spaceship moving west and eaten by a p5 oscillator at the
     east end.

Spiral decay (a.k.a. A glider's work is never done)   (4/10/91;
                                                       736 bytes)
     Four puffers travel north, east, south, and west, making boats.
     A glider spirals among them, deleting them.

Thue generator   (by Bill Gosper, date unknown (1987?); 817 bytes)
     This produces 4 lines of blinkers representing the transcendental
     number .110110111110110111110110110..., where the n'th bit is 1
     if n is not divisible by 3 and is the complement of the (n/3)'th
     bit if n is divisible by 3.

Exponential aperiodic   (1/7/91; 808 bytes)
     A glider bounces between a fixed reflector and the output of a
     glider puffer.  Each round trip takes 3 times as long as the
     preceding one, so cells along the path never become periodic.
     (This is based on an ancient pattern in which a glider bounces
     between the outputs of 2 glider puffers.)

Linear aperiodic   (by Bill Gosper, 5/83; 865 bytes)
     A glider bounces back and forth between a fixed reflector and
     a diagonal line of boats produced by 2 glider puffers.  Each
     round trip takes 120 gens longer than the preceding one, so cells
     along the path never become periodic.

Binary counter   (2/9/90; 2147 bytes)
     A p736 (= 46 * 2^4) gun based on 4 boat-bits forming a binary
     counter.  (A boat-bit is a memory device in which a bit of
     information is represented as the presence or absence of a boat
     adjacent to a snake (or eater or beacon or ...).  Hitting the
     boat-bit with a glider changes its state.  The transition from 1
     to 0 can be detected by another glider.)

Pseudorandom number generator with p46 logic   (by Bill Gosper, 10/89
                                                or earlier; 1309 bytes)
     This generates a p46 pseudorandom sequence of gliders, defined
     by the recursion  a[n] = a[n-1] EQV a[n-12].  The period of the
     sequence is 3255, so the gun has period 46*3255 = 149730.

Pseudorandom LWSS generator with p46 logic   (by Bill Gosper, 10/89 or
                                              earlier; 1408 bytes)
     Similar to the above, but this emits LWSSs instead of gliders,
     and the recursion is  a[n] = a[n-1] EQV a[n-19].  The sequence
     has period 413385, so the gun's period is  46*413385 = 19015710.

Pseudorandom number generator with p120 logic   (3/21/92; 1078 bytes)
     This generates a p120 pseudorandom sequence of gliders, defined
     by the recursion  a[n] = a[n-1] XOR a[n-11].  The period of the
     sequence is 1533, so the gun has period 120*1533 = 183960.

Infinite glider hotel   (by David Bell, 10/9/92; 5334 bytes)
     Two pairs of Corderships are pulling slowly apart, with an
     ever-lengthening glider track between them.  Every 1920 gens
     another glider is injected into the track, joining the ones
     already circulating there.


Glider syntheses
----------------
Natural unix   (11/16/92; 182 bytes)
     Two R-pentominoes produce the p6 oscillator "unix" and some junk.

Syntheses of 27 still lifes   (11/8/92; 8261 bytes)
     Syntheses found by running random patterns on tori with
     various forms of symmetry.

Syntheses of 14 still lifes   (11/16/92; 3147 bytes)
     More of the same.

Syntheses of 29 still lifes   (5/30/93; 6829 bytes)
     More of the same.

Syntheses of 109 still lifes   (2/11/93; 8046 bytes)
     Syntheses of still lifes by David Buckingham.

Hustler synthesis   (3/12/91, from notes by David Buckingham,
                     dated 1/30/90; 2727 bytes)
     A 123 glider synthesis of the p3 billiard table oscillator
     "hustler".  The steps of the construction were figured out
     by David Buckingham.  (I put them together, probably less
     efficiently than Buckingham could have.)

Billiard table syntheses   (collection assembled 1/25/93; 1441 bytes)
     Glider syntheses, by David Buckingham, of 4 billiard table
     oscillators: p8 Hertz oscillator, p3 MIT oscillator,
     p2 scrubber, and an unnamed p3.

END OF FILE